1. 背景
FM 模型是最近几年提出的模型，凭借其在数据量比较大并且特征稀疏的情况下，忍让能够得到优秀的性能和效果，屡次在各大公司举办的 CTR 预估比赛中获得不错的战绩。
在计算广告领域，点击率 CTR（click-through rate）和转化率 CVR（conversion rate）是衡量广告流量的两个关键指标。准确的估计 CTR、CVR 对于提高流量的价值，增加广告收入有重要的指导作用。预估 CTR、CVR，业界常用的方法由人工特征工程 + LR（Logistic Regression）、GBDT（Gradient Boosting Decision Tree）+LR、FM（Factorization Machine）和 FFM（Field-aware Factorization Machine）模型。在这些模型中，FM 和 FFM 近年来表现突出，分别在 Criteo 和 Avazu 举办的 CTR 预测竞赛中夺得冠军。
2. FM 模型原理推导
因子分解机（Factorization Machine，简称 FM），又称分解机。是由德国康斯坦茨大学的 Steffen Rendle（现任职于 Google）于 2010 年最早提出的，旨在解决大规模稀疏数据下的特征组合问题。在系统介绍 FM 之前，先了解一下在实际场景中，稀疏数据是怎样产生的。
假设一个广告分类的问题，根据用户和广告位相关的特征，预测用户是否点击了广告。元数据如下：
| Clicked? | Country | Day | Ad_type |
|---|---|---|---|
| 1 | USA | 26/11/15 | Movie |
| 0 | China | 1/7/14 | Game |
| 1 | China | 19/2/15 | Game |
“Clicked？” 是 label，Country、Day、Ad_type 是特征。由于三种特征都是 categorical 类型的，需要经过独热编码（One-Hot Encoding）转换成数值型特征。
| Clicked? | Country=USA | Country=China | Day=26/11/15 | Day=1/7/14 | Day=19/2/15 | Ad_type=Movie | Ad_type=Game |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
由上表可以看出，经过 One-Hot 编码之后，大部分样本数据特征是比较稀疏的。上面的样例中，每个样本有 7 维特征，但平均仅有 3 维特征具有非零值。实际上，这种情况并不是此例独有的，在真实应用场景中这种情况普遍存在。例如，CTR/CVR 预测时，用户的性别、职业、教育水平、品类偏好、商品的品类等，经过 One-Hot 编码转换后都会导致样本数据的稀疏性。特别是商品品类这种类型的特征，如商品的末级品类约有 550 个，采用 One-Hot 编码生成 550 个数值特征，但每个样本的这 550 个特征，有且仅有一个是有效的（非零）。由此可见，数据稀疏性是实际问题中不可避免的挑战。
One-Hot 编码的另一个特点就是导致特征空间大。例如，商品品类有 550 维特征，一个 categorical 特征转换为 550 维数值特征，特征空间剧增。
同时通过观察大量的样本数据可以发现，某些特征经过关联之后，与 label 之间的相关性就会提高。如：“USA”与 “Thanksgiving”、“China” 与“Chinese New Year”这样的关联特征，对用户的点击有着正向的影响。换句话说，来自 “China” 的用户很可能会在 “Chinese New Year” 有大量的浏览、购买行为，而在 “Thanksgiving” 却不会有特别的消费行为。这种关联特征与 label 的正向相关性在实际问题中是普遍存在的，如 “化妆品” 类商品与 “女” 性，“球类运动配件”的商品与 “男” 性，“电影票”的商品与 “电影” 品类偏好等。因此，引入两个特征的组合是非常有意义的。
表示特征之间的关联，最直接的方法的是构造组合特征。样本中特征之间的关联信息在 one-hot 编码和浅层学习模型（如 LR、SVM）是做不到的。目前工业界主要有两种手段得到组合特征：
- 1）人工特征工程（数据分析＋人工构造）；
- 2）通过模型做组合特征的学习（深度学习方法、FM/FFM 方法）
本章主要讨论 FM 用来学习特征之间的关联。多项式模型是包含特征组合的最直观的模型。在多项式模型中，特征 $xi$ 和 $xj$ 的组合采用 $ xi$ 表示，即 $xi$ 和 $xj$ 都非零时，组合特征 $ xixj$ 才有意义。从对比的角度，本文只讨论二阶多项式模型。模型的表达式如下：
$y(x)=w0+∑{i=1}^nwix_i+∑{i=1}^n∑{j=i+1}^nw{ij}x_ix_j$
其中，$n$ 代表样本的特征数量，$xi$ 是第 ii 个特征的值，$w0、w_i、w{ij}$ 是模型的参数。
从这个公式可以看出，组合特征的参数一共有 $n(n−1)/2$ 个，任意两个参数都是独立的。然而，在数据稀疏性普遍存在的实际应用场景中，二次项参数的训练是很困难的。其原因是，回归模型的参数 $w$ 的学习结果就是从训练样本中计算充分统计量（凡是符合指数族分布的模型都具有此性质），而在这里交叉项的每一个参数 wijwij 的学习过程需要大量的 $xi$、$xj$ 同时非零的训练样本数据。由于样本数据本来就很稀疏，能够满足 “$xi$ 和 $xj$ 都非零” 的样本数就会更少。训练样本不充分，学到的参数 wijwij 就不是充分统计量结果，导致参数 $w_{ij}$ 不准确，而这会严重影响模型预测的效果（performance）和稳定性。
那么，如何解决二次项参数的训练问题呢？矩阵分解提供了一种解决思路。在 Model-based 的协同过滤中，一个 rating 矩阵可以分解为 user 矩阵和 item 矩阵，每个 user 和 item 都可以采用一个隐向量表示。比如在下图中的例子，我们把每个 user 表示成一个二维向量，同时把每个 item 表示成一个二维向量，两个向量点积就是矩阵中 user 对 item 的打分。
类似地，所有二次项参数 $w{ij}$ 可以组成一个对称阵 $W$（为了方便说明 FM 的由来，对角元素可以设置为正实数），那么这个矩阵就可以分解为 $W=V^TV$，$V$ 的第 $j$ 列便是第 $j$ 维特征的隐向量。换句话说，每个参数 $w{ij}=⟨v_i,v_j⟩$，这就是 FM 模型的核心思想。因此，FM 的模型方程为（本文不讨论 FM 的高阶形式）
$y(x)=w0+\sum {i=1}^nwix_i+\sum{i=1}^n\sum_{j=i+1}^n⟨vi,vj⟩x_ix_j \ \ \ \ \ \ ···（2）$
其中，$v_i$ 是第 i 维特征的隐向量，$⟨⋅,⋅⟩$ 代表向量点积，计算公式为
$⟨vi,v_j⟩=\sum{f=1}^kv{i,f}·v{j,f}$
隐向量的长度为 $k(k<<n)$，包含 k 个描述特征的因子。
具体解读一下这个公式
- 线性模型 + 交叉项：直观地看 FM 模型表达式，前两项是线性回归模型的表达式，最后一项是二阶特征交叉项（又称组合特征项），表示模型将两个互异的特征分量之间的关联信息考虑进来。用交叉项表示组合特征，从而建立特征与结果之间的非线性关系。
- 交叉项系数 → 隐向量内积：由于 FM 模型是在线性回归基础上加入了特征交叉项，模型求解时不直接求特征交叉项的系数 $w{ij}$（因为对应的组合特征数据稀疏，参数学习不充分），故而采用隐向量的内积 $⟨vi,vj⟩$ 表示 $w{ij}$。具体的，FM 求解过程中的做法是：对每一个特征分量 $xi$ 引入隐向量 $vi＝(vi,1,vi,2,⋯,vi,k)$，利用 $viv^T_j$ 内积结果对交叉项的系数 $w{ij}$ 进行估计，公式表示：$ŵ ij=v_iv^T_j$
根据上式，二次项的参数数量减少为 $kn$ 个，远少于多项式模型的参数数量。
此外，参数因子化表示后，使得 $x_hx_i$ 的参数与 $x_ix_j$ 的参数不再相互独立。这样我们就可以在样本系数的情况下相对合理地估计 FM 模型交叉项的参数。具体地：
$⟨vh,v_i⟩=\sum{f=1}^k v{h,f}·v{i,f}$
$⟨vi,v_j⟩=\sum{f=1}^k v{i,f}·v{j,f}$
$xhx_i$ 与 $x_ix_j$ 的系数分别为 $⟨v_h,v_i⟩$ 和 $⟨v_i,v_j⟩$，它们之间有共同项 $v_i$，也就是说，所有包含 $x_i$ 的非零组合特征（存在某个 $j≠i$, 使得 $x_ix_j≠0$）的样本都可以用来学习隐向量 $v_i$，这在很大程度上避免了数据系数行造成参数估计不准确的影响。而在多项式模型中，$w{hi}$ 和 $w_{ij}$ 是相互独立的。
显而易见，公式 (2) 是一个通用的拟合方程，可以采用不同的损失函数用于解决回归、二元分类等问题，比如可以采用 MSE（Mean Square Error）损失函数来求解回归问题，也可以采用 Hinge、Cross-Entropy 损失来求解分类问题。当然，在进行二元分类时，FM 的输出需要经过 Sigmoid 变换，这与 Logistic 回归是一样的。
| FM 应用场景 | 损失函数 | 说明 |
|---|---|---|
| 回归 | 均方误差（MSE）损失 | Mean Square Error，与平方误差类似 |
| 二类分类 | Hinge/Cross-Entopy 损失 | 分类时，结果需要做 sigmoid 变换 |
| 排序 |
直观上看，FM 的复杂度是 $O(kn^2)$，但是，通过下面的等价转换，可以将 FM 的二次项化简，其复杂度可以优化到 $O(kn)$，即：
$\sum{i=1}^n\sum{j=i+1}^n⟨vi,v_j⟩x_i,x_j=\frac{1}{2}\sum{f=1}^k[(\sum{i=1}^nv{i,f}xi)^2-\sum{i=1}^nv_{i,f}^2x_i^2]$
下面给出详细推导：
$\sum{i=1}^n\sum{j=i+1}^n⟨vi,v_j⟩x_ix_j \ =\frac{1}{2}\sum{i=1}^n\sum{f=1}^n⟨v_i,v_j⟩x_ix_j-\frac{1}{2}\sum{i=1}^n⟨vi,v_i⟩x_ix_i \ =\frac{1}{2}(\sum{i=1}^n\sum{j=1}^n\sum{f=1}^kv{i,f}v{j,f}xix_j-\sum{i=1}^n\sum{f=1}^kv{i,f}v{i,f}x_ix_i) \ =\frac{1}{2}\sum{f=1}^k[(\sum{i=1}^nv{i,f}xi)·(\sum{j=1}^nv{j,f}x_j)-\sum{i=1}^nv{i,f}^2x_i^2] \ =\frac{1}{2}\sum{f=1}^k[(\sum{i=1}^nv{i,f}xi)^2- \sum{i=1}^nv_{i,f}^2x_i^2]$
解读第一步到第二部，这里用 A 表示系数矩阵 V 的上三角元素，B 表示对角线上的交叉项系数。由于系数矩阵 V 是一个对称阵，所以下三角和上三角相等，有下式成立：
$A=\frac{1}{2}(2A+B)-\frac{1}{2}B$
其中，
$A=\sum{i=1}^n\sum{j=i+1}^n⟨vi,v_j⟩x_ix_j,B=\sum{i=1}^n⟨v_i,v_j⟩x_ix_i$
把上式合并，得到等价的 FM 模型公式：
$\hat y(\mathbf{x}) = w0+ \sum{i=1}^d wi x_i + \frac{1}{2} \sum{f=1}^k \left( \left(\sum{i=1}^dv{i,f}xi \right) ^2 – \sum{i=1}^d v_{i,f}^2x_i^2\right) $
如果用随机梯度下降（SGD）法学系模型参数。那么模型各个参数的梯度如下：
$\frac{\partial}{\partial\theta}y\left(x\right)=\left{\begin{array}{l} 1,\ \ if\ \theta\ is\ w0\left (\textrm{常数项}\right)\ x_i,\ if\ \theta\ is\ w_i\left (\textrm{线性项}\right)\ x_i\underset{j=1}{\overset{n}{\varSigma}}v{j,f}xj-v{i,f}x{i}^{2},\ if\ \theta\ is\ v{i,f}\left(\textrm{交叉项}\right)\ \end{array}\right.$
其中，$v_{j,f}$ 是隐向量 $vj$ 的第 f 个元素。
由于 $Σ^n{j=1}v{j,f}xj$ 只与 f 有关，在参数迭代过程中，只需要计算第一次所有 f 的 $Σ^n{j=1}v{j,f}x_j$，就能够方便地得到所有 $v{i,f}$ 的梯度。显然，计算所有 f 的 $Σ^n{j=1}v{j,f}xj$ 的复杂度是 O$(kn)$；已知 $Σ^n{j=1}v_{j,f}x_j$ 时，计算每个参数梯度的复杂度是 $O(n)$；得到梯度后，更新每个参数的复杂度是 $O(1)$；模型参数一共有 $nk+n+1$ 个。因此，FM 参数训练的时间复杂度为 $O(kn)$
3. FM 的优 3 势
综上可知，FM 算法可以在线性时间内完成模型训练，以及对新样本作出预测，所以说 FM 是一个非常高效的模型。FM 模型的核心作用可以概括为以下三个：
- 1）FM 降低了交叉项参数学习不充分的影响：one-hot 编码后的样本数据非常稀疏，组合特征更是如此。为了解决交叉项参数学习不充分、导致模型有偏或不稳定的问题。作者借鉴矩阵分解的思路：每一维特征用 k 维的隐向量表示，交叉项的参数 $w{ij}$ 用对应特征隐向量的内积表示，即 $<v_i,v_j⟩$。这样参数学习由之前学习交叉项参数 $w{i,j}$ 的过程，转变为学习 $n$ 个单特征对应 k 维隐向量的过程。很明显，单特征参数（k 维隐向量 $vi$）的学习要比交叉项参数 $w{ij}$ 学习的更加充分。示例说明：
假如有 10w 条训练样本，其中出现女性特征的样本数为 3w，出现男性特征的样本数为 7w，出现汽车特征的样本数为 2000，出现化妆品的样本数为 1000。特征共现的样本数如下：
| 共现交叉特征 | 样本数 | 注 |
|---|---|---|
| <女性，汽车> | 500 | 同时出现 <女性，汽车> 的样本数 |
| <女性，化妆品> | 1000 | 同时出现 <女性，化妆品> 的样本数 |
| <男性，汽车> | 1500 | 同时出现 <男性，汽车> 的样本数 |
| <男性，化妆品> | 0 | 样本中无此特征组合项 |
<女性，汽车> 的含义是女性看汽车广告。可以看到，但特征对应的样本数远大于组合特征对应的样本数。训练时，但特征参数相比交叉项特征参数会学习地更充分。因此，可以说 FM 降低了因数据稀疏，导致交叉项参数学习不充分的影响。
2）FM 提升了模型预估能力。依然看上面的示例，样本中没有没有 <男性，化妆品> 交叉特征，即没有男性看化妆品广告的数据。如果用多项式模型来建模，对应的交叉项参数 $w{男性，化妆品}$ 是学不出来的，因为数据中没有对应的共现交叉特征。那么多项式模型就不能对出现的男性看化妆品广告场景给出准确地预估。
FM 模型是否能得到交叉项参数 $w{男性，化妆品}$ 呢？答案是肯定的。由于 FM 模型是把交叉项参数用对应的特征隐向量内积表示，这里表示为 $w{男性，化妆品}$=，即用男性特征隐向量 $v{男性}$ 和化妆品特征隐向量 $v{化妆品}$ 的内积表示交叉项参数 $w{男性，化妆品}$。由于 FM 学习的参数就是单特征的隐向量，那么男性看化妆品广告的预估结果可以用 $w_{男性，化妆品}$ 得到。这样，即便训练集中没有出现男性看化妆品广告的样本，FM 模型仍然可以用来预估，提升了预估的能力。
3）FM 提升了参数学习效率：这个显而易见，参数个数由 $(n^2+n+1)$ 变为 $(nk+n+1)$ 个，模型训练复杂度也由 $O(mn2)$ 变为 $O(mnk)$。$m$ 为训练样本数。对于训练样本和特征数而言，都是线性复杂度。此外，就 FM 模型本身而言，它是在多项式模型基础上对参数的计算做了调整，因此也有人把 FM 模型称为多项式的广义线性模型，也是恰如其分的。从交互项的角度看，FM 仅仅是一个可以表示特征之间交互关系的函数表法式，可以推广到更高阶形式，即将多个互异特征分量之间的关联信息考虑进来。例如在广告业务场景中，如果考虑 User-Ad-Context 三个维度特征之间的关系，在 FM 模型中对应的 degree 为 3。
最后一句话总结，FM 最大特点和优势：FM 模型对稀疏数据有更好的学习能力，通过交互项可以学习特征之间的关联关系，并且保证了学习效率和预估能力。
与其他模型相比，它的优势如下：
- FM 是一种比较灵活的模型，通过合适的特征变换方式，FM 可以模拟二阶多项式核的 SVM 模型、MF 模型、SVD++ 模型等；
- 相比 SVM 的二阶多项式核而言，FM 在样本稀疏的情况下是有优势的；而且，FM 的训练 / 预测复杂度是线性的，而二项多项式核 SVM 需要计算核矩阵，核矩阵复杂度就是 N 平方。
- 相比 MF 而言，我们把 MF 中每一项的 rating 分改写为 $r_{ui}∼β_u+γ_i+x^T_uy_i$，从公式 (2) 中可以看出，这相当于只有两类特征 $u$ 和 $i$ 的 FM 模型。对于 FM 而言，我们可以加任意多的特征，比如 user 的历史购买平均值，item 的历史购买平均值等，但是 MF 只能局限在两类特征。SVD++ 与 MF 类似，在特征的扩展性上都不如 FM，在此不再赘述。